#include <bits/stdc++.h>
using namespace std;

struct edge_t {
   int to, pr, la;
   edge_t() { to = 0, pr = 0, la = 0; }
};

struct aux_t {
   int fa, de, si;
   aux_t() { fa = 0, de = 0, si = 0; }
};

#define LG2MAXN lg2maxN
struct tree_t {
   int top, lg2maxN, size;
   edge_t* e;
   aux_t* aux;
   bool hasRoot;
   int** anc;  // anc[1000][LG2MAXN + 1];
   tree_t(int len, bool hasRoot) : size(len), hasRoot(hasRoot) {
      e = new edge_t[hasRoot ? size : size * 2]();
      aux = new aux_t[size]();
      lg2maxN = log2(size) + 1;
      top = 0;
      anc = new int*[size * 2];
      for (int i = 0; i < size * 2; i++)
         anc[i] = new int[LG2MAXN];
   }

   void linkHasRoot(int p, int c) {
      e[++top].to = c, e[top].pr = e[p].la, e[p].la = top;
      aux[top].fa = p;
   }

   void link(int p, int c) {
      linkHasRoot(p, c);
      if (!hasRoot)
         linkHasRoot(c, p);
   }

   void CalcAux(int x, int fath) {
      if (hasRoot)
         CalcAuxHasRoot(x);
      else
         CalcAuxNoRoot(x, fath);
   }

   void CalcAuxHasRoot(int x) {
      // aux[x].fa = e[x].to;
      int fath = aux[x].fa;
      aux[x].de = aux[fath].de + 1;
      aux[x].si = 1;
      anc[x][0] = fath;
      for (int i = 1; i <= LG2MAXN; i++) anc[x][i] = anc[anc[x][i - 1]][i - 1];
      for (int i = e[x].la; i; i = e[i].pr) {
         CalcAux(e[i].to, x);
         aux[x].si += aux[e[i].to].si;
      }
   }

   void CalcAuxNoRoot(int x, int fath) {
      aux[x].fa = fath;
      aux[x].de = aux[fath].de + 1;
      aux[x].si = 1;
      anc[x][0] = fath;
      for (int i = 1; i <= LG2MAXN; i++) anc[x][i] = anc[anc[x][i - 1]][i - 1];
      for (int i = e[x].la; i; i = e[i].pr) {
         if (e[i].to != fath) {
            CalcAux(e[i].to, x);
            aux[x].si += aux[e[i].to].si;
         }
      }
   }

   int LCA_a1(int x, int y) {
      while (x != y) {
         if (aux[x].de > aux[y].de)
            x = aux[x].fa;
         else
            y = aux[y].fa;
      }
      return x;
   }

   int LCA_MoT(int x, int y) {
      if (aux[x].de < aux[y].de)
         swap(x, y);
      int delta = aux[x].de - aux[y].de;
      for (int j = 0; j < LG2MAXN; j++)
         if ((1 << j) & delta) x = anc[x][j];
      if (x == y) return x;
      for (int j = LG2MAXN; j >= 0; j--)
         while (anc[x][j] != anc[y][j]) x = anc[x][j], y = anc[y][j];
      return anc[x][0];
   }

   ~tree_t() {
      delete e;
      delete aux;
   }

   void view(int n) {
      printf("%3s%5s%5s%5s%5s%5s%5s\n", "i", "fa", "de", "si", "da", "pr", "la");

      for (int i = 0; i < n; i++) {
         aux_t& ax = aux[i];
         printf("%3d%5d%5d%5d%5d%5d%5d\n", i, ax.fa, ax.de, ax.si, e[i].to, e[i].pr, e[i].la);
      }
   }

   int getMaxDepNode() {
      int x = 0;
      for (int i = 0; i < size; i++)
         if (aux[i].de > aux[x].de)
            x = i;

      return x;
   }

   int diameter(int& p1, int& p2) {
      p1 = getMaxDepNode();
      for (int i = 0; i < size; i++)
         aux[i].de = 0;

      CalcAuxNoRoot(p1, 0);
      p2 = getMaxDepNode();
      return aux[p2].de;
   }
};

tree_t tr2(1000, true);
tree_t tr(1000, false);
int main() {
   // tree_t tr2;
   int x, y, n = 0;
   while (cin >> x >> y) {
      n = max(n, x);
      n = max(n, y);
      tr.link(x, y);

      // tr2.link(x, y);
   }
   tr.CalcAux(1, 0);
   tr.view(2 * n);
   // tr2.CalcAux(1, 0);
   // tr2.view(2 * n);
   x = 3, y = 11;
   printf("LCA:\n");
   for (int i = 1; i < 2 * n; i++) {
      int cnt = 0;
      for (int j = i + 1; j < 2 * n; j++) {
         if (tr.e[i].to && tr.e[j].to && tr.e[i].to != tr.e[j].to) {
            x = tr.e[i].to, y = tr.e[j].to;
            printf("   (%2d,%2d)=%2d(%2d)", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
            if (++cnt % 5 == 0)
               printf("\n");
         }
      }
      printf(".\n");
   }
   // printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x,
   // y));
   x = 6, y = 8;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   x = 8, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));

   printf("%d = d(", tr.diameter(x, y));
   printf("%d, %d)\n", x, y);
   return 0;
}
